#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;

int cal(vector<vector<int>>& grid, vector<vector<int>>& mem, int i, int j) {
    int row = grid.size() - 1;
    int col = grid[0].size() - 1;
    if (mem[i][j] > 0) {
        return mem[i][j];
    } else {
        if (i == row && j == col) {
            return grid[i][j];
        }
        if (i < row && j == col) {
            int res = grid[i][j] + cal(grid, mem, i + 1, j);
            return mem[i][j] = res;
        } else if (i == row && j < col) {
            int res = grid[i][j] + cal(grid, mem, i, j + 1);
            return mem[i][j] = res;;
        } else {
            int res = grid[i][j] + min(cal(grid, mem, i + 1, j), cal(grid,mem, i, j+1));
            return mem[i][j] = res;
        }
    }
}
int minPathSum(vector<vector<int>>& grid) {
    int row = grid.size();
    int col = grid[0].size();
    // mem
    vector<vector<int>> mem(row, vector<int>(col, 0));
    return cal(grid, mem, 0, 0);
}

int main(int argc, char const *argv[])
{
    vector<vector<int>> grid = {
                                {1,3,1},
                                {1,5,1},
                                {4,2,1}
                               };

    int pathSum = minPathSum(grid);
    cout << pathSum << endl;
    return 0;
}
